package countsort

import "fmt"

//  这是一个非比较的排序
// 思想是什么： 在一段数字中间，创建一个数组用来计数，数组长度可用用来取数
// 假如数据区间是0-60 ，那么数组的长度就是61,0-60相当于数组的下标，
// 数据出现，就在对应数组中加一，
// 量大，取值范围较小，比如高考成绩，人数50万，取值范围就是0到750
func CountSort(arr []int) []int {
	res := make([]int, len(arr))
	fmt.Println(res)
	tmp := make([]int, 10)
	fmt.Println(tmp)
	var j int = 0
	for _, value := range arr {
		fmt.Printf("value = %d \n", value)
		tmp[value]++
		fmt.Printf("tmp[value] = %d\n", tmp[value])
	}
	fmt.Println("--------fff----------")
	fmt.Println(len(tmp))
	for i := 0; i < len(tmp); i++ {
		for tmp[i] > 0 {
			res[j] = i
			tmp[i]--
			j++
		}
	}
	return res
}

// 你说是就是喽，我能怎么想，你让我怎么想，这些都是你出的注意，事情也都是你做的，
// 现在出了问题，你就在这甩/锅？难不成当初是有人拿着刀拿架在你脖子逼你的吗？----
// 无理取闹也要有个限度！

// 计数排序稳定算法
// 时间，空间复杂度都是n+k 
func CountSortStable(arr []int) []int {
	arrLen := make([]int, 10)
	res := make([]int, len(arr))
	for _, value := range arr {
		arrLen[value]++
	}
	fmt.Printf("arrLen:%v", arrLen)
	
	for i := 1; i<len(arrLen);i++{
		arrLen[i] = arrLen[i]+arrLen[i-1]
	}
	fmt.Printf("arrLen2:%v", arrLen)
	for i:=len(arr)-1;i>=0;i--{
		
		res[arrLen[arr[i]]-1] = arr[i]
		arrLen[arr[i]]--
	}
	fmt.Printf("res:%v", res)
	return res

}